package com.tgy.leetcode.backtracking;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020-11-21 10:48
 *
 * https://leetcode-cn.com/problems/combination-sum/
 */
public class _39_组合总和 {

    private int[] candidates;

    private int target;

    private List<List<Integer>> lists;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {


        lists = new LinkedList<>();

        if (Objects.isNull(candidates) || candidates.length == 0 || target <= 0) {

            return lists;
        }

        this.candidates = candidates;
        this.target = target;

        Arrays.sort(this.candidates);

        if (target < candidates[0]) {

            return lists;
        }


        LinkedList<Integer> candidateList = new LinkedList<>();
        sum(0,0,candidateList);


        return lists;
    }

    private void sum(int index, int sum, LinkedList<Integer> candidateList) {

        if (index >= this.candidates.length) {

            return;
        }
        int tmpSum;
        for (int i = index; i < this.candidates.length; i++) {

             tmpSum = sum + this.candidates[i];

            // 元素是从小到大，后面肯定是大于 target的，所以直接break跳出循环
            if (tmpSum > this.target) {

                break;
            }
            candidateList.add(this.candidates[i]);
            if (tmpSum < this.target) {
                // 小于
                sum(i,tmpSum,candidateList);
            }else if (tmpSum == this.target){
                // 等于
                this.lists.add(new LinkedList<>(candidateList));
            }
            candidateList.removeLast();
        }
    }

}
